package algorithm;

/**
 * 斐波那契数列
 */
public class Test {
    /**
     * 斐波那契数列
     * 时间复杂度O(2^n)
     * 空间复杂度O(1)
     * @param n
     * @return
     */
    public int Fibonacci (int n) {
        if(n==1||n==2)
            return 1;
        return Fibonacci(n-1)+Fibonacci(n-2);

    }

    /**
     * 斐波那契数列
     * 时间复杂度O(n)
     * 空间复杂度O(n)
     * @param n
     * @return
     */
    public int Fibonacci1 (int n) {
        int[] F = new int[n+1];
        F[1]=1;
        F[2]=1;
        for(int i=3;i<=n;i++){
            F[i]=F[i-1]+F[i-2];
        }
        return F[n];
    }

    /**
     * 斐波那契数列
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     * @param n
     * @return
     */
    public int Fibonacci2 (int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 1;
        int fn=0;
        int fn1=1;//第n-1项
        int fn2=1;//第n-2项
        for(int i=3;i<=n;i++){
            fn=fn1+fn2;
            fn2=fn1;
            fn1=fn;

        }
        return fn;
    }

}
